8 割點、橋、雙連通元件

現在讓我們回到無向圖的演算法。給一張圖，要判斷這張圖是否為連通圖相當簡單：只要做一次 BFS 或 DFS 就可以了。但是，如果我們想知道當某個點壞掉、或是某條邊壞掉的時候，這張圖是否仍然連通，那麼問題就會變得有趣許多。

如果去掉一個點(同時失去所有其相鄰的邊)，就會讓整張圖斷開的話，我們稱這個點為割點 (cut-vertex)、或者稱為關節點 (articulation point)。如果去掉一條邊，就會讓整張圖斷開，那麼我們稱這條邊為一座橋。

8.1 尋找關節點的 Tarjan 演算法

Robert Tarjan 可以說是 DFS 演算法的開疆始祖。許多與 DFS 有關的演算法都以 Tarjan 為名。包含了前一節描述的強連通元件演算法，也有一個線性版本是 Tarjan 發表的(可以參考 Tarjan 在 1972 年的論文)。以今天的關節點問題來說，Tarjan 描述了一個使用 DFS 能找到所有關節點的演算法：
第一步：首先，找出一個 DFS 樹，樹上每個節點都有一個深度 depth(x)。
第二步：對於每一個節點 x，計算 lowpt(x)，什麼是 lowpt(x) 呢？就是 x 這個點的所有子孫節點(包含 x 自身) 能夠透過非樹邊 (也就是回溯邊 back edges) 能夠抵達的最淺深度。這一步可以在線性時間內算完。

因此，對於一個節點 x 來說，如果其所有子孫能夠有一條回溯邊，到得了其祖先節點，那麼 x 一定不是關節點。反之，如果這個節點某個子孫節點 c 其 lowpt(c) >= depth(x)，那麼代表拿掉 x 以後，可以將 x 的祖先與 x 的子孫分開。因此， x 在這個情形下一定是關節點。

8.2 判斷圖是否為雙連通

如果整張圖都不存在關節點，那麼我們便稱這張圖為雙連通的。因此我們知道存在一個線性 O(V+E) 時間的演算法，判斷這張圖是否為雙連通。

8.X 冷笑話

台北的捷運路網是否存在關節點呢？其實不存在，因為可以有雙連站，因此台北捷運是雙連通的，直通雙連。

參考資料

https://codeforces.com/blog/entry/71146
Tarjan 最早描述 DFS 的論文：https://epubs.siam.org/doi/10.1137/0201010

今天好混QQ